Normal approximation and fourth moment theorems for monochromatic triangles

Given a graph sequence denote by T₃(G_n) the number of monochromatic triangles in a uniformly random coloring of the vertices of G_n with colors. In this paper we prove a central limit theorem (CLT) for T₃(G_n) with explicit error rates, using a quantitative version of the martingale CLT. We then relate this error term to the well-known fourth-moment phenomenon, which, interestingly, holds only when the number of colors satisfies . We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any , which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of T₃(G_n), whenever . Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in [7].     

Maximizing and minimizing the number of generalized colorings of trees

We classify the trees on $n$ vertices with the maximum and the minimum number of certain generalized colorings, including conflict-free, odd, non-monochromatic, star, and star rainbow vertex colorings. We also extend a result of Cutler and Radcliffe on the maximum and minimum number of existence homomorphisms from a tree to a completely looped graph on $q$ vertices.     

对自由落体的诺维科夫时间与牛顿绝对时间关系讨论

文章首先将史瓦西黑洞场中自由下落质点的固有时(诺维科夫坐标时)公式,由自然单位制化成了国际单位制中的形式.然后,根据牛顿第二定律和万有引力定律,推导出了自由下落质点经历的绝对时间公式,进而证明了广义相对论中自由落体经历的固有时,恰好等于牛顿力学给出的绝对时间.最后,对自由下落质点在黑洞内外经历的时间进行了特例计算.     

双子佯谬与星际航行

计算了在两个假想的星际航行方案中,与"双子佯谬"相关的时间差别.这种差别体现了惯性与非惯性参考系经历的时间有绝对差异,而不再是"相对"效应.     

Clique-cutsets beyond chordal graphs

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (eg, the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. Furthermore, we obtain polynomial -bounding functions for these classes.     

Erratum: The average degree of an edge-chromatic critical graph II

In the article “The average degree of an edge-chromatic critical graph II” by Douglas R. Woodall (J. Graph Theory 56 (2007), 194-218), it was claimed that the average degree of an edge-chromatic critical graph with maximum degree $\mathrm{\Delta }$ is at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+1\right)$ if $\mathrm{\Delta }⩾2$, at least $\text{◂+▸}\frac{2}{3}\mathrm{\Delta }+1$ if $\mathrm{\Delta }⩾8$, and at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+2\right)$ if $\mathrm{\Delta }⩾15$. Unfortunately there were mistakes in the proof of the last two of these results, which are now proved only if $\mathrm{\Delta }⩾18$ and $\mathrm{\Delta }⩾30$, respectively.